//
// Created by Administrator on 2024/1/4.
//
/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素
 *查找第一个/ 最后一个值大于等于给定值的元素
 *
 * 讲解:https://blog.csdn.net/whynotwu/article/details/117887036
 * */


#include <iostream>
#include <vector>

using namespace std;

// 查找第一个值等于给定值的元素
int binarySearchForFirst(vector<int> &n, int target)
{
    int left = 0, right = n.size() - 1;
    int mid;
    while (left <= right)
    {
        mid = (left + right) >> 1;
//        cout << left << mid << right << endl;
        if (target > n[mid])
        {
            left = mid + 1;
        } else if (target < n[mid])
        {
            right = mid - 1;
        } else
        {
            if (mid == 0 || n[mid - 1] != target)
                return mid;
            else
                right = mid - 1;
        }
    }
    return -1;

}

// 查找最后一个值等于给定值的元素
int binarySearchForLast(vector<int> &n, int target)
{
    int left=0,right=n.size()-1;
    int mid;
    while(left<=right)
    {
        mid=left+(right-left)/2;
//        mid = (left + right) >> 1;
        if(target>n[mid])
            left=mid+1;
        else if(target<n[mid])
            right=mid-1;
        else
        {
            if(mid>=n.size() || n[mid+1]!=target)
                return mid;
            else
                left=mid+1;
        }
    }
    return -1;
}

int main()
{
    vector<int> l = {-11, -5, 0, 0, 0,0, 2, 3, 5, 7, 9, 10};
    int target = 0;
    cout << binarySearchForFirst(l, target)<<endl;
    cout << binarySearchForLast(l, target)<<endl;
    return 0;
}